package szte.objectorgy.collections;

/**
 * Linked list implementation of the list data structure.
 * 
 * @author Csilla-Andrea KAPUSI
 * @param <T>
 *            The type of the elements stored in this collection.
 */
public class LinkedList<T extends Comparable<T>> implements List<T> {

	protected ListElement<T> head;
	protected ListElement<T> end;
	protected int size;

	public LinkedList() {
		head = null;
		end = null;
		size = 0;
	}

	@Override
	public void add(T element) {
		if (head == null) {
			head = new ListElement<T>(element, null);
			end = head;
		} else {
			ListElement<T> newElement = new ListElement<T>(element, null);
			end.setNext(newElement);
			end = newElement;
		}
		size++;
	}

	@Override
	public void addAll(Collection<T> collection) {
		Iterator<T> it = collection.getIterator();
		while (it.hasNext()) {
			add(it.next());
		}
	}

	@Override
	public void clear() {
		head = null;
		end = null;
		size = 0;
	}

	@Override
	public boolean contains(T element) {
		return indexOf(element) != -1;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public Iterator<T> getIterator() {
		return new LinkedListIterator();
	}

	@Override
	public void remove(T element) {
		if (head.element.equals(element)) {
			head = head.next;
			size--;
		} else {
			ListElement<T> link = head;
			while ((link.next != null) && (!link.next.element.equals(element))) {
				link = link.next;
			}
			if (link.next != null) {
				if(link.next.equals(end)) {
					end = link;
				}
				link.next = link.next.next;
				size--;
			}
		}
	}

	@Override
	public void removeAll(Collection<T> collection) {
		Iterator<T> it = collection.getIterator();
		while (it.hasNext()) {
			remove(it.next());
		}
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public Object[] toArray() {
		int index = 0;
		Object[] obj = new Object[size];
		Iterator<T> it = getIterator();
		while (it.hasNext()) {
			obj[index++] = it.next();
		}
		return obj;
	}

	@Override
	public void add(int index, T element) {
		if (index == size) {
			add(element);
		} else {
			if (index < size) {
				ListElement<T> newElement = new ListElement<T>(element, null);
				if (index == 0) {
					newElement.setNext(head);
					head = newElement;
				} else {
					int i = 0;
					ListElement<T> link = head;
					while (i != (index - 1)) {
						link = link.next;
						i++;
					}
					newElement.next = link.next;
					link.next = newElement;
				}
				size++;
			} else {
				throw new IndexOutOfBoundsException();
			}
		}
	}

	@Override
	public T get(int index) {
		if (index < size) {
			int i = 0;
			ListElement<T> link = head;
			while (i != index) {
				link = link.next;
				i++;
			}
			return link.element;
		} else {
			throw new IndexOutOfBoundsException();
		}
	}

	@Override
	public int indexOf(T element) {
		int index = 0;
		Iterator<T> it = getIterator();
		while (it.hasNext()) {
			if (it.next().equals(element)) {
				return index;
			}
			index++;
		}
		return -1;
	}

	@Override
	public void set(int index, T element) {
		if (index < size) {
			int i = 0;
			ListElement<T> link = head;
			while (i != index) {
				link = link.next;
				i++;
			}
			link.element = element;
		} else {
			throw new IndexOutOfBoundsException();
		}
	}

	public class ListElement<E> {
		private E element;
		private ListElement<E> next;

		public ListElement(E e, ListElement<E> n) {
			element = e;
			next = n;
		}

		public E getElement() {
			return element;
		}

		public void setElement(E element) {
			this.element = element;
		}

		public ListElement<E> getNext() {
			return next;
		}

		public void setNext(ListElement<E> next) {
			this.next = next;
		}
	}
	
	public String toString() {
		StringBuilder sb = new StringBuilder();
		Iterator<T> it = getIterator();
		while (it.hasNext()) {
			sb.append(it.next() + "; ");
		}
		
		return sb.toString();
	}

	public class LinkedListIterator implements Iterator<T> {

		ListElement<T> link = head;

		@Override
		public boolean hasNext() {
			return link != null;
		}

		@Override
		public T next() {
			T data = link.element;
			link = link.next;
			return data;
		}

	}
}
